1. Field of the Invention
Embodiments of the invention relate generally to memory devices and memory systems. More particularly, embodiments of the invention relate to devices and methods adapted to efficiently manage nonvolatile memory, such as a flash memory.
2. Description of the Related Art
A nonvolatile memory maintains data previously written to its constituent memory cell even when the memory does not receive power. Flash memory is one specific type of nonvolatile memory which is widely used in computers, memory cards, etc. Flash memory is a preferred memory choice in many applications because its memory cells may be electrically erased in bulk manner. More recently, flash memory has found increasing use on such portable information devices as cell phones, PDAs, and digital cameras. More generally, flash memory is being used with increasing frequency as a replacement for hard disk and other types of data storage.
Contemporary flash memory is classified into NOR type and NAND type according to a connection state between respective cells and bit lines. NOR flash memory has a high read speed and a low write speed and is thus used mainly for code memory. In contrast, NAND flash memory has a high write speed and a low price per unit area and is thus used mainly for large-capacity storage. However, as compared to other types of memory, flash memory provides relatively high speed read operations at a relatively low unit cost. Flash memory is characterized by the execution of an erase operation before a write operation, wherein the unit of data being written is larger than the of data erased. This characteristic makes it difficult to use flash memory as a main memory. It also makes it difficult for flash memory to use general hard disk filing systems even in applications where flash memory is used as an auxiliary memory. Accordingly, a flash translation layer (FTL) is commonly used between the file system and flash memory in order to make the unique programming characteristics inherent in flash memory transparent to the host device.
The FTL serves to map a logical address generated by the file system into a physical address of the flash memory, at which the erase operation is performed, during a flash memory write operation.
Examples of conventional address mapping methods are disclosed in U.S. Pat. Nos. 5,404,485; 5,937,425; and 6,381,176, the subject matter of which is hereby incorporated by reference. The FTL typically uses an address mapping table to perform a rapid address mapping operation. In general, the address mapping table is formed (i.e., created and/or stored) in relatively expensive static random access memory (SRAM).
Using a FTL address mapping function, a host device may operationally recognize flash memory as substituted for a hard disk or SRAM, and may thus access the flash memory in the same manner as the hard disk. The FTL may be embodied in hardware separate and independent to the host device, or it may be embodied in a device driver internal to the host device.
The FLT address mapping function may be broadly classified as page-level address mapping and block-level address mapping according to its basic address mapping unit, wherein the page is a unit of write data and the block is a unit erase data. Page-level address mapping provides excellent performance because it converts an address with greater accuracy, but it is expensive to implement because it requires a large-sized address mapping table. Block-level address mapping requires a relatively smaller sized address mapping table because only roughly converts an address, but it is expensive to manage because it must erase and update a whole data block even when only a single page in the block requires update. In addition, block-level address mapping may undesirably break data consistency when a fault occurs during its operation.
To overcome these problems, a log-block scheme that stores data logarithmically in a manner similar to that of log-structured file systems (LFS) has recently been proposed. The log-block scheme combines aspects of page-level address mapping and block-level address mapping. The log-block scheme processes relatively large quantities of Input/Output (I/O) data on a block basis and processes relatively small quantities of I/O data on a page basis. However, an address mapping method used within the log-block scheme requires three (3) address mapping tables, such as a block mapping table, a log-block mapping table, and a log mapping table. Thus, the log-block scheme generally involves a complex process of controlling I/O operations using such tables.
As described above, the conventional FTL uses a variety of the conventional address mapping methods. However, use of these conventional address mapping methods fails to prevent an increase in the size of the address mapping table tending to result from increased data storage capacities for emerging host devices. Accordingly, a requirement exists for an address mapping table that more efficiently manages address mapping information related to a flash memory. Such an address mapping table should occupy a relatively small memory even when the memory capacity of the incorporating host device expands.